#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,ssse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define LLMax LLONG_MAX
#define LLMin LLONG_MIN
#define Max INT_MAX
#define Min INT_MIN
#define FOR1(i,a,b) for(int i=(a);i<(b);i++)
#define FOR2(i,a,b) for(int i=(a);i<=(b);i++)
#define DWN(j,b,a) for(int j=(b);j>=(a);j--)
#define SETN1(a) memset(a,-1,sizeof(a))
#define SET0(a) memset(a,0,sizeof(a))
#define pb push_back
#define mk make_pair
#define Re register int
#define IOS ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
//#define int long long
//#define int __int128
#define lowbit(x) ((x)&(-x))
const int INF=0x3f3f3f3f;
const int NINF=-INF-1;
const double PI=acos(-1);
const int mod=1e9+7;
const int maxn=1e6+50;
const double eps=1e-7;
using namespace std;
void read() {}
template<typename T,typename... T2>inline void read(T &x,T2 &... oth) { x=0;int ch=getchar(),f=0;while(ch<'0'||ch>'9') { if (ch=='-') f=1;ch=getchar();}while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}if(f)x=-x;read(oth...);}
inline void write(int a) {if(a<0) putchar('-'),a=-a;if(a>=10)write(a/10);putchar(a%10+48);}
int n,m,q;
int a[maxn],b[maxn];
struct Tree {
    int l,r;
    int sum,lazy;
}tree[maxn<<2];
inline void push_up(int i) {
    tree[i].sum=max(tree[i<<1].sum,tree[i<<1|1].sum);
}
inline void push_down(int i) {
    if(tree[i].lazy) {
        int k=tree[i].lazy;
        tree[i<<1].lazy+=k,tree[i<<1|1].lazy+=k;
        tree[i<<1].sum+=k,tree[i<<1|1].sum+=k;
        tree[i].lazy=0;
    }
}
inline void build(int i,int L,int R) {
    tree[i].l=L,tree[i].r=R;
    if(L==R) return;
    int mid=L+R>>1;
    build(i<<1,L,mid),build(i<<1|1,mid+1,R);
}
inline void updata(int i,int L,int R,int val) {
    if(tree[i].l>=L&&tree[i].r<=R) {
        tree[i].sum+=val;
        tree[i].lazy+=val;
        return;
    }
    push_down(i);
    if(tree[i<<1].r>=L) updata(i<<1,L,R,val);
    if(tree[i<<1|1].l<=R) updata(i<<1|1,L,R,val);
    push_up(i);
}
inline int query(int i) {
    if(tree[i].l==tree[i].r) {
        return tree[i].l;
    }
    push_down(i);
    if(tree[i<<1|1].sum>0) return query(i<<1|1);
    else if(tree[i<<1].sum>0) return query(i<<1);
    else return -1;
}
signed main() {
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //IOS;
    read(n,m);
    build(1,1,1e6+5);
    FOR2(i,1,n) {
        read(a[i]);
        updata(1,1,a[i],1);
    }
    FOR2(i,1,m) {
        read(b[i]);
        updata(1,1,b[i],-1);
    }
    read(q);
    while(q--) {
        int opt,pos,x;read(opt,pos,x);
        if(opt==1) {
            updata(1,1,a[pos],-1);
            a[pos]=x;
            updata(1,1,a[pos],1);
            write(query(1));
        }
        else {
            updata(1,1,b[pos],1);
            b[pos]=x;
            updata(1,1,b[pos],-1);
            write(query(1));
        }
        putchar('\n');
    }
    return 0;
}
